modeltheoryfandomcom-20200213-history
Categoricity
A theory T'' is '''categorical' if any two models of T'' are isomorphic. If \lambda is a cardinal, ''T is said to be \lambda '-categorical' if T'' has a unique model of cardinality \lambda , up to isomorphism. Both of these conditions imply that ''T is complete (i.e., all models of T'') are elementarily equivalent. For \lambda -categoricity, this is the Łoś-Vaught Test. Due to the Löwenheim-Skolem Theorem, almost no theories are categorical. Specifically, if ''T has an infinite model, then the upward Löwenheim-Skolem theorem ensures the existence of a strictly bigger model. Therefore T'' has at least two non-isomorphic models, and is not categorical. Consequently, the only categorical theories are the complete theories of finite structures. The concept of \lambda -categoricity is a weakening of categoricity which has the advantage of being a non-trivial notion, while still implying completeness. Examples * DLO, the theory of dense linear orders, is \aleph_0 -categorical, but not \lambda -categorical for uncountable \lambda . * The theory of the random graph is \aleph_0 -categorical, but not \lambda -categorical for uncountable \lambda . * If ''F is a finite field, the theory of infinite F''-vector spaces is \lambda -categorical for every infinite cardinal \lambda . * The theory of divisible infinite abelian groups (i.e., '''Q'-vector spaces) is \lambda -categorical for uncountable \lambda , but not \aleph_0 -categorical. * For p'' a prime number or 0, the theory ACFp of characteristic ''p algebraically closed fields is \lambda -categorical for uncountable \lambda , but not \aleph_0 -categorical. The last three examples can be seen roughly as follows. If F'' is a field, then an ''F-vector space V'' is determined up to isomorphism by its dimension (cardinality of a basis). If ''F is finite and V'' is infinite, then the dimension of ''V equals the cardinality of V''. Hence any two ''F-vector spaces of the same size must be isomorphic. If F'' is infinite, such as '''Q', then the cardinality of V'' is |F| + \lambda , where \lambda is the dimension of ''V over F''. In particular, since '''Q' is countable, if |V| or \lambda is uncountable, then |V| = \lambda . So for uncountable Q'''-vector spaces, the cardinality determines the dimension, and hence the isomorphism class. On the other hand, there are non-isomorphic countable '''Q-vector spaces, such as Q''' and 'Q'2. So countable categoricity fails. The case of ACF is handled similarly, using the fact that an algebraically closed field's isomorphism class is determined uniquely by the characteristic and the cardinality of a transcendence base over the prime field. The \aleph_0 -categoricity of DLO and the random graph can be seen using the Ryll-Nardzewski Theorem, by proving quantifier elimination in these theories and showing that there are few n-types over the empty set. On the other hand, these theories fail to be uncountably categorical because they are not stable. Łoś-Vaught Test '''Theorem: If T'' is \lambda -categorical for some \lambda \ge |T| , and all models of ''T are infinite, then T'' is complete. ''Proof: Let M'' and ''N be two models of T''. We want to show that ''M ≡ N''. By the Löwenheim-Skolem Theorem, we can find ''M' ''and ''N' ''of cardinality \lambda , with ''M' ≡ M and N' ≡ N. Then M' ''and ''N' ''are both models of ''T, because they are elementarily equivalent to models of T''. By \lambda -categoricity, it follows that ''M' ''and ''N' ''are isomorphic. Hence they are elementarily equivalent. Now : M \equiv M' \equiv N' \equiv N , so ''M ≡ N''. QED This provides a relatively straightforward way of proving the completeness of the theory ACFp of algebraically closed fields in a fixed characteristic. As a consequence, one can conclude that the complex numbers are elementarily equivalent to the algebraic numbers. The completeness of ACF0 also implies that the theory of the complex numbers, as a pure field, is decidable. Consequently, Hilbert's Tenth Problem can be solved over the complex numbers. The completeness of ACF0 can also be seen as a form of the Lefschetz principle. Countably Categorical Theories '''Ryll-Nardzewski Theorem:' Let M'' be a countable structure in a countable language. The following are equivalent: * The complete theory of ''M is \aleph_0 -categorical. * For every n'', there are finitely many ''n-types over the empty set, in M''. * If Aut(''M) denotes the group of automorphisms of M'', then the action of Aut(''M) on Mn has finitely many orbits, for every n''. * ??? ''Proof sketch: Let T'' be the complete theory of ''M. Let Sn(Ø) denote the set of n''-types over the empty set. This is a compact boolean space. If ''Sn(Ø) is infinite, then it is not discrete, so there is some non-isolated point p'' ∈ ''Sn(Ø). Now by the Omitting Types Theorem, we can produce a countable model N'' of ''T in which the type p'' is not realized. By compactness and downward Löwenheim-Skolem, we can also produce a countable model of ''T in which the type p'' ''is realized. This implies that T'' is not \aleph_0 -categorical. So countable categoricity implies the finiteness of the type spaces. Conversely, suppose we know that the type spaces over the empty set are finite. Then given two countable models ''M and N'' of ''T, one can prove that M'' and ''N are isomorphic by a back-and-forth argument, implying countable categoricity. In fact, one can prove from the back-and-forth argument that if x ∈ M and y ∈ N are two tuples realizing the same type over the empty set, then there is an isomorphism from M'' to ''N sending x'' to ''y. In the case where M'' = ''N, this means that the automorphisms of M'' must act transitively on the set of ''n-tuples in M'' realizing each type. Since there are only finitely many ''n-types, there must be finitely many orbits. So the second bullet point implies the first and third bullet points. On the other hand, the third bullet point implies the second bullet point. Specifically, suppose that Mn has finitely many orbits under Aut(M''). Any 0-definable subset of ''Mn must be a finite union of orbits, and therefore there are only finitely many 0-definable subsets of Mn. Then the Stone space Sn(Ø) is dual under Stone duality to a finite boolean algebra, and is therefore itself finite. QED From the Ryll-Nardzewski Theorem, one can prove that DLO and the theory of the Random Graph are \aleph_0 -categorical. For example, in DLO, an n''-type is completely determined by specifying the relative order of the ''n-variables. There are only finitely many possibilities, so the space of n''-types is finite. In the Random Graph, an ''n-type is determined by specifying which of the n'' variables are equal, and which are connected. Again, there are only finitely many possibilities, so the type spaces are finite. More generally, one has '''Lemma:' If T'' is a theory with quantifier-elimination in a signature with no constants, no functions, and finitely many relations, none of which are nullary, then ''T is complete and \aleph_0 -categorical. Proof: Completeness follows because every sentence \phi must be equivalent to a quantifier-free sentence, but the lack of constant symbols and nullary relations means that there are no atomic formulas without free variables, and so the only quantifier-free sentences are ⊤ and ⊥. In particular, \phi is equivalent modulo T'' to one of ⊤ or ⊥, so either \phi or \neg \phi is in ''T. For \aleph_0 -categoricity, note that the lack of function symbols ensures that in the free variables x''1, ... ''x''n, there are only finitely many possible atomic formulas. Consequently, there are only finitely many quantifier-free formulas, ensuring that the type spaces over the empty set are finite. Then by the Ryll-Nardzewski Theorem, ''T is countably categorical. QED Uncountable Categorical Theories Morley's Theorem: Let T'' be a countable theory. If ''T is \lambda -categorical for one uncountable cardinal, then T'' is \lambda -categorical for all uncountable cardinals. Because of Morley's Theorem, one knows that (countable) theories must fall into four classes: * Totally categorical: \lambda -categorical for every infinite cardinal \lambda . This includes the theories of ''F-vector spaces, for F'' a finite field, as well as the theory of equality. * Countably categorical: this includes DLO and the random graph * Uncountably categorical: this includes ACFp and the theory of infinite divisible abelian groups. * Not \lambda -categorical for any \lambda . This includes many theories of interest, such as RCF, ACVF, DCF, and ACFA. ''Proof outline: First one shows that T'' is stable and in fact |totally transcendental using Ehrenfeucht-Mostowski models. Next one uses the ability to stretch Vaughtian pairs in totally transcendetal theories to show that ''T cannot have Vaughtian pairs. From this one shows that infinity is definable in T''. Using this and Cantor-Bendixson rank, one can show the existence of strongly minimal sets definable in the prime model of ''T. The algebraic closure operation on this strongly minimal set is a pregeometry. One associates to each model M'' of ''T the cardinality of a basis for this pregeometry. Because of no Vaughtian pairs, a model M'' must be constructible over such a basis. From this, one sees that ''M is determined up to isomorphism by the cardinality of the basis. From this, one can conclude that T'' is \lambda -categorical for all uncountable \lambda in roughly the same way that one proves this directly for ACFp or the theory of '''Q'-vector spaces. (In these two examples, the resulting pregeometries are the usual pregeometries for algebraic independence and linear independence, respectively.) ∎ In fact, this argument allows one to prove the (Baldwin-Lachlan?) theorem, that if T'' is an uncountably categorical theory, then the number of ''countable models of T'' is either 1 or \aleph_0 . Much of stability theory was motivated by the problem of analyzing the structure of uncountably categorical theories. Totally Categorical Theories A theory if '''totally categorical' if it is \lambda -categorical for all infinite \lambda . A great deal is known about the structure of totally categorical theories... For example, Zilber proved that if T'' is totally categorical, then the underlying pregeometry is always modular. Using this, he was able to prove that ''T is not finitely axiomatizable. This elementary-sounding statement requires a considerable amount of stability theory to prove.